package hpp.problems;

import java.util.Scanner;

/**
 * 给出两个字符串（可能包含空格）,找出其中最长的公共连续子串,输出其长度。
 * 测试用例:
 Sit it out G
 Sit down and shut up
 对应输出应该为:
 4
 */
public class Problem53 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String s1 = in.next();
            String s2 = in.next();
            System.out.print(LCS(s1, s2));
//            System.out.println(findMaxSame(s1, s2).length());
        }

    }

    //    动态规划思想：
//    准备一个N+1 * N+1大小的二维数组dp，置0。
//    dp[i][j]代表s1的0-i位置与s2的0-j位置中连续公共子串的最大长度。
//    则有：
//    如果s1[i] == s2[j]，dp[i][j] = dp[i-1][j-1] + 1;
//    否则，dp[i][j] = 0;
//    记录最大长度即可。
    public static int LCS(String a,String b){
        int la = a.length();
        int lb = b.length();
        int max = 0;
        int [][]dp = new int[1+la][1+lb];
        for(int i = 1;i<=la;i++){
            for(int j = 1;j<=lb;j++){
                if(a.charAt(i-1) == b.charAt(j-1)){
                    dp[i][j] = 1+dp[i-1][j-1];
                }else{
                    dp[i][j] = 0;
                }
                max=Math.max(max,dp[i][j]);
            }
        }
        return max;
    }


    /**
     * 输出字符串
     * @param s1
     * @param s2
     * @return
     */
    private static String findMaxSame(String s1, String s2) {
        int l1 = s1.length();
        String maxSame = "";
        String subString = "";
        for (int i = 0; i < l1; i++) {
            for (int j = i+1; j <=l1; j++) {
                subString = s1.substring(i, j);
                if (s2.contains(subString)) {//TODO:真的不会超时吗？
                    maxSame = subString.length() > maxSame.length() ? subString : maxSame;
                } else {
                    break;
                }
            }
        }
        return maxSame;
    }
}
